package number_08_01;

public class Solution {
    public int waysToStep(int n) {
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        int f0 = 1, f1 = 2, f2 = 4;
        for (int i = 4; i <= n; i++) {
            int f3 = (f0 + (f1 + f2) %1000000007 ) % 1000000007;
            f0 = f1;
            f1 = f2;
            f2 = f3;
        }
        return f2;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().waysToStep(61));
    }
}
